The present invention relates generally to digital display systems. More particularly, the present invention relates to systems and methods for color quantization, i.e., producing a display image having a fewer number of colors from an original image having a greater number of colors.
A particular color may be defined by the relative intensities of certain primary colors making up that color. As such, the color may be thought of as a point in multidimensional space, the axes of which represent the individual primary colors. For example, the primary colors red, green and blue may define a three-dimensional space having coordinates R, G and B ("RGB space").
Digital image recording devices can record images containing millions of different colors. Typically, the image is recorded as a multiplicity of adjacent "pixels," i.e., picture elements. Each pixel contains a color, which is often represented by a 24-bit digital number. The 24-bit digital number is generally divided into three 8-bit segments which represent the respective coordinates along the three axes of the RGB color space. In this case, an individual pixel of an original recorded image may contain any one from a possible 2.sup.24 (16,777,216) colors.
If a 24-bit color monitor is used to reproduce the original image, a display image equivalent to the original image is easily obtained. However, monitors of this type are often prohibitively expensive. As such, most color monitors in use today store colors in a lookup table having respective memory locations addressed by an 8-bit index. Therefore, such monitors can simultaneously display at most 2.sup.8 (256) different colors. This lookup table may be referred to, along with the collection of colors therein, as a "color table."
The problem of displaying a color image defined by n bits per pixel on a device that is restricted, via a lookup table, to a total number of colors indexed by m bits (where m&lt;n) is referred to as "color quantization." Color quantization encompasses the following two functions: (1) color selection, i.e., determining the smaller number of colors that will be used in the display image; and (2) color mapping, i.e., once the smaller number of colors are chosen, determining how these colors are to be distributed among the individual pixels of a display image.
A number of color quantization methods have been utilized in the past and are disclosed in the relevant literature. One such technique is referred to as the "uniform" method. The "uniform" method simply determines each color table entry by its index. Specifically, the color table index is divided into three bit fields corresponding to the primary color components of the color table entry. In the case of an 8-bit index (0-255), a common choice of field sizes is three bits for red, three bits for green, and two bits for blue (reflecting the relative insensitivity of the human eye to variations in blue). Such a choice therefore gives an index range of "0" to "7" for red and green, and "0" to "3" for blue. The actual color table entries are then determined by appropriate scaling of the index. For example, if each entry of the lookup table can store a 24-bit digital number, the respective colors may be determined by scaling the red and green fields by thirty-two (32) and the blue field by sixty-four (64).
Color table entries are mapped to individual pixels of the display image based on the color appearing in corresponding pixels of the original image. Specifically, the original image color is divided and truncated to produce an index value. In the above exemplar, this may be accomplished by dividing red and green components of the original image color by thirty-two (32) and the blue component by sixty-four (64). The remainders are dropped to give the respective red, green and blue bit fields of the chosen index. This index identifies the color table entry that will be used for the respective pixel.
A second color quantization method is the "popularity" method. The "popularity" method chooses the colors appearing most frequently in the original image as the respective color table entries. For example, the 256 most popular colors of the original image would be entered into a color table indexed by an 8-bit word. Colors in the original image may then be mapped to the color table entries by finding the entry which is closest in the multidimensional color space. This closest color may then be displayed in the corresponding pixel of the display image. The uniform method and the popularity method are discussed in P. Burger and D. Gillies, Interactive Computer Graphics (1989).
Another color quantization method is the "median-cut" method. Systems utilizing this technique assign a weight to each color used in the original image based on the number of times it is used. The multidimensional color space is then divided into boxes such that the sum of the weights of the colors in each box is approximately equal. The color table entries are determined by taking the weighted average of the image colors contained in each of the boxes. The average color for a particular box will be used to represent any color in the original image which falls within that box.
A discussion of the median cut quantization method may be found in P. Heckbert, "Colour Image Quantization for Frame Buffer Display", ACM Computer Graphics, Vol. 16, pp. 297-307, 1982. In this reference, the author notes that the median cut quantization method is likely to introduce objectionable color bands in large, smoothly shaded areas. To ameliorate this condition, the author suggests that a dithering technique be employed. This dithering technique is a variation on a known error diffusion algorithm, in which quantization error introduced at each pixel is distributed to its neighbors whose color assignments have not been made. Color banding, which would otherwise appear in the display image, is somewhat reduced by this dithering technique.
An additional color quantization method is referred to as "octree quantization." Like the median-cut method, this method divides the multidimensional color space and assigns weights to the colors in the original image. Octree quantization, however, adopts an approach of regular subdivision. Colors occurring in the original image which are close together in the color space are grouped together and averaged by weight. Grouping continues until all colors in the original image have been grouped and the number of groups is equal to the number of desired color table entries. Mapping is accomplished by using the representative color for every image color which falls in the group. This technique is disclosed in M. Gervautz and W. Purgathofer, "A Simple Method for Color Quantization: Octree Quantization," Proc. of Computer Graphics International 1988, pp. 219-31, May 1988.
A color quantization technique based on the notion of "simulated annealing" has been proposed in E. Fiume & M. Ouellette, "On Distributed, Probabilistic Algorithms for Computer Graphics", Proc. Graphics Interface '89, pp. 211-18 (1989). The simulated annealing technique can be described as a non-deterministic walk on an energy surface that is changing shape under the control of a "cooling" schedule. The energy of a particular color table may be defined as the sum of the quantization error introduced at each pixel by the use of that color table. A particular color table is selected by a gradient descent algorithm that occasionally accepts small ascending moves. Original image pixels are then mapped to the table entries which are closest thereto in the multidimensional color space.
Devices and systems are known in the art for recording and reproducing images and are disclosed in various prior art patents. For example, U.S. Pat. No. 4,907,075 to Braudaway discloses a histogram-based color selection method. U.S. Pat. No. 4,926,250 to Konishi discloses a color image recording and reproducing apparatus. This device reproduces color based on a histogram approach. U.S. Pat. No. 4,710,806 to Iwai discloses a digital display system with color lookup table. This system also uses a histogram approach to select the entries to be included in the color lookup table. Other patents of interest include U.S. Pat. No. 4,994,927 to Dixit, U.S Pat. No. 4,675,750 to Collins, and U.S. Pat. No. 4,998,165 to Lindstrom.
It can thus be seen that conventional schemes generally resolve the problem of color quantization using variations of a histogram approach. Histogram methods, however, will often fail to select the optimal colors for the color table because they focus on the colors appearing in individual pixels rather than colors which may appear in the image as a whole. For example, distinct colors may be used often in the original image, yet presented in adjacent pixels in a checkerboard arrangement. Due to spatial color integration, a blended color, rather than the distinct colors of the respective pixels, will be seen by the human eye. A histogram approach, however, would choose the distinct colors, rather than the blended color, as for inclusion into the color table. Additionally, a histogram method may select colors from the color table which differ only slightly from the original colors but which differ from each other in such a way that the blend of the selected colors is significantly different from the blend of the original colors. Again, the reconstructed image actually seen by the human eye will be significantly different than the original image. Thus, while conventional techniques will often yield satisfactory results, they will frequently introduce errors and distortion into the display image.